package leetcode.array;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

/**
 * @program: java_learning
 * @description
 * @author: 辛旭初
 * @create: 2020-10-26 11:52
 **/
public class Queation56 {

    static public int[][] merge(int[][] intervals) {

        //对数组开始时区进行排序。
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        //创建栈
        Stack<Integer> stack = new Stack<Integer>();
        //A代表栈顶开始时区，B代表栈顶结束时区。
        //先将第一个时区数组放入栈，方便接下来的操作。
        int A = intervals[0][0];
        int B = intervals[0][1];
        stack.push(A);
        stack.push(B);

        //遍历时区
        for(int i = 1; i < intervals.length; i++){
            //a,b是即将进行判断的时区
            int a = intervals[i][0];
            int b = intervals[i][1];

            //如果栈顶结束时区大于判断的开始时区，
            //说明有交叉需要合并
            if(B >= a){
                //合并栈顶弹栈，更新位B,中最大的即可，同时将最大的压入栈。被合并一个，counts--
                stack.pop();
                B = (int)Math.max(B,b);
                stack.push(B);
            }else if(B < a){
                //如果没有交叉，不需要合并，那么a,b入栈更新即可。
                stack.push(a);
                stack.push(b);
                A = a;
                B = b;
            }
        }

        //因为时区必定成双存在，倒叙遍历弹栈放入ans数组中即可。
        int [][] ans = new int[stack.size()/2][2];
        for(int i = ans.length - 1; i >= 0; i--){
            ans[i][1] = stack.pop();
            ans[i][0] = stack.pop();
        }

        return ans;
    }

    /**
     * 难点在于生成所看到的结果如何存放在二维数组里
     *
     * @param intervals
     * @return
     */
    static public int[][] merge1(int[][] intervals){
        //对数组开始时区进行排序。
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);

    }

    public static void main(String[] args) {

       int[][] intervals = new int[][]{{1,3},{15,18},{8,10},{2,6}};
       int[][] data = merge1(intervals);

        for (int i = 0; i < data.length; i++) {
            int[] tmp =  data[i];
            for (int j = 0; j < tmp.length; j++) {
                System.out.print(tmp[j]+" ");
            }
            System.out.println("");
        }
    }
}
